#ifndef __FOURSUMCOUNT_H__
#define __FOURSUMCOUNT_H__
#include <vector>
#include <unordered_map>
using namespace std;

/*
* leetcode 454. 四数相加 II
*/

/*
* 给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n
* 请你计算有多少个元组 (i, j, k, l) 能满足：
* 0 <= i, j, k, l < n
* nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
* 
* 注意: 不需要去重
*/

/*
* 思路:
* 1.使用哈希表
* 2.将四个数组的和, 拆解成两两数组的和, 用于降低时间复杂度 (n^2)
* 
* 例: 数组 A B C D
* 使用一个哈希map, 记录 A + B 的值以及出现的次数
* 
* 然后再去计算 C + D 的值, 当在 hashmap 中找到了 0 - (C + D) 的值时, 则表示找到了对应组合
* 最后再加上组合出现的次数, 意为计算出元组的个数
*/
int FourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4)
{
	int result = 0;
	unordered_map<int, int> hashMap;	//key 表示 A + B 的和, value 表示 出现的次数(即组合数)
	
	//记录组合出现的次数
	for (int num1 : nums1) {
		for (int num2 : nums2) {
			if (hashMap.find(num1 + num2) != hashMap.end())
				hashMap[num1 + num2]++;

			else
				hashMap.insert({ num1 + num2, 1 });
		}
	}

	//累加组合数
	for (int num3 : nums3) {
		for (int num4 : nums4) {
			if (hashMap.find(0 - (num3 + num4)) != hashMap.end())
				result += hashMap[0 - (num3 + num4)];
		}
	}

	return result;
}

#endif // !__FOURSUMCOUNT_H__
